package targetToOffer.twethDay;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Godc
 * @description 使用大小堆搭配，非常巧妙
 */
public class MedianFinder {
    // A是小顶堆存较大的一半，B是大顶堆存小的一般
    Queue<Integer> A,B;

    /**
     * 如果N为偶数，则media=(大顶堆+小顶堆)/2,如果为奇数，返回A的堆顶
     */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x,y)->y-x);
    }

    /**
     * 当 m=n（即 N 为 偶数）：需向 A 添加一个元素。实现方法：将新元素 num 插入至 B ，再将 B 堆顶元素插入至 A ；
     * 当 m≠n（即 N 为 奇数）：需向 B 添加一个元素。实现方法：将新元素 num 插入至 A ，再将 A 堆顶元素插入至 B
     * 比如你想向A添加一个元素，不能直接添加入A,因为可能num输入较小的B堆，先加入B，再将B的堆加入A，保证A始终是较大的以班
     * @param num
     */
    public void addNum(int num) {
        if(A.size()!=B.size()){
            A.offer(num);
            B.offer(A.poll());
        }else{
            B.offer(num);
            A.offer(B.poll());
        }
    }
    // 如果元素个数N为偶数，则A=B=N/2,如果元素个数为奇数，则A=(N+1)/2，B=(N-1)/2
    public double findMedian() {
        return A.size()==B.size()?(A.peek()+B.peek())/2:A.peek();
    }
}
